package SwordOffer;

public class Sword_Offer_11 {

    /*public int minArray(int[] numbers) {
        int min = Integer.MAX_VALUE;
        for (int number : numbers) {
            if (min > number) {
                min = number;
            }
        }
        return min;
    }*/

    public int minArray(int[] numbers) {
        return dps(numbers, 0, numbers.length - 1);
    }

    private int dps(int[] numbers, int begin, int end) {
        if (begin == end) {
            return numbers[begin];
        } else if (begin + 1 == end) {
            return Math.min(numbers[begin], numbers[end]);
        } else {
            int mid = (begin + end + 1) / 2;
            if (numbers[begin] == numbers[mid] && numbers[mid] == numbers[end]) {
                return Math.min(dps(numbers, begin, mid - 1), dps(numbers, mid, end));
            } else if (numbers[begin] <= numbers[mid] && numbers[mid] <= numbers[end]){
                return numbers[begin];
            } else if (numbers[mid] <= numbers[begin] && numbers[mid] <= numbers[end]){
                return dps(numbers, begin + 1, mid);
            } else if (numbers[begin] <= numbers[mid] && numbers[end] <= numbers[mid]) {
                return dps(numbers, mid + 1, end);
            } else {
                System.out.println("意外情况");
                return 0;
            }
        }
    }

    public static void main(String[] args) {
        Sword_Offer_11 model = new Sword_Offer_11();
        System.out.println(model.minArray(new int[]{3,4,5,1,2}));
        System.out.println(model.minArray(new int[]{2,2,2,0,1}));
        System.out.println(model.minArray(new int[]{1, 2, 3, 4, 5, 6}));
    }
}
